#include <iostream>
#include <functional>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
using namespace std;

struct Node {
	int index;
	int val;
	Node(int a, int b) :index(a), val(b) {}
};

int main()
{
	string type; cin >> type; //cout << type << endl;
	bool DUN = 0, GN = 0; // 有向无向、带不带权
	if (type == "DG")  DUN = 1, GN = 0;
	if (type == "DN")  DUN = 1, GN = 1;
	if (type == "UDG") DUN = 0, GN = 0;
	if (type == "UDN") DUN = 0, GN = 1;
	int n; cin >> n; vector<string> nodes(n);
	map<string, int> ntoi; // node to index
	for (int i = 0; i < n; ++i) {
		cin >> nodes[i]; if (i) cout << ' '; cout << nodes[i];
		ntoi[nodes[i]] = i;
	}	cout << endl;
	string flag("0"); vector<list<Node>> graph_out(n), graph_in(n);
	int k; cin >> k; //cout << k << endl;
	vector<vector<int>> path(k, vector<int>(2 + GN)); // 带权的话 给权值留个位置
	for (int i = 0; i < k; ++i) cin >> path[i][0] >> path[i][1];
	if (GN) for (int i = 0; i < k; ++i)  cin >> path[i][2];
	for (auto& v : path) {
		graph_out[v[0]].push_front(Node(v[1], (GN ? v[2] : 0)));
		graph_in[v[1]].push_front(Node(v[0], (GN ? v[2] : 0)));
		if (!DUN) graph_out[v[1]].push_front(Node(v[0], (GN ? v[2] : 0))), graph_in[v[0]].push_front(Node(v[1], (GN ? v[2] : 0)));
	}
	for (int i = 0; i < n; ++i) {
		if (i)cout << endl;
		cout << nodes[i];
		for (auto e : graph_out[i]) {
			cout << "->" << e.index;
			if (GN) cout << "(" << e.val << ")";
		}
	}
	cout << "\n\n";
	
	vector<int> tgts;
	vector<int> node_ve(n); // <i, j> : [j] = max([j], [i] + <i, j>)
	vector<int> in(n), out(n);
	for (int i = 0; i < n; ++i) in[i] = graph_in[i].size(), out[i] = graph_out[i].size();
	queue<int> q_in, q_out;
	for (int i = 0; i < n; ++i) if (!in[i]) q_in.push(i), node_ve[i] = 0;
	int last_ve = 0;
	while (q_in.size()) {
		int k = q_in.size();
		while (k--) {
			int cur = q_in.front(); q_in.pop();
			for (auto e : graph_out[cur]) {
				if (--in[e.index] == 0) q_in.push(e.index);
				if (last_ve < (node_ve[e.index] = max(node_ve[e.index], node_ve[cur] + e.val))) {
					last_ve = node_ve[e.index];
					tgts.clear();
					tgts.push_back(e.index);
				}
				else if (last_ve == node_ve[e.index]) {
					tgts.push_back(e.index);
				}
			}
		}
	}
	vector<int> node_vl(n, last_ve); // <i, j> : [i] = min([i], [j] - <i, j>)
	for (int i = 0; i < n; ++i) if (!out[i]) q_out.push(i);
	while (q_out.size()) {
		int k = q_out.size();
		while (k--) {
			int cur = q_out.front(); q_out.pop();
			for (auto e : graph_in[cur]) {
				if (--out[e.index] == 0) q_out.push(e.index);
				node_vl[e.index] = min(node_vl[e.index], node_vl[cur] - e.val);
			}
		}
	}

	for (int i = 0; i < n; ++i) cout << nodes[i] << '\t' << node_ve[i] << '\t' << node_vl[i] << '\n';
	cout << endl;

	vector<list<int>> graph(n);
	// e(i, j) = ve[i]
	// l(i, j) = vl[j] - w
	for (int i = 0; i < n; ++i) {
		for (auto& cur : graph_out[i]) {
			int j = cur.index;
			int e = node_ve[i];
			int l = node_vl[j] - cur.val;
			cout << "<" << nodes[i] << ',' << nodes[j] << ">\t" << e << "\t" << l << endl;
			if (e - l == 0) graph[i].push_front(j);
		}
	}
	
	vector<int> visited(n);
	vector<vector<int>> paths;
	vector<int> curpath;
	function<void(int)>
		dfs = [&](int cur) {
		if (find(tgts.begin(), tgts.end(), cur) != tgts.end()) {
			paths.emplace_back(curpath.begin(), curpath.end());
			return;
		}
		for (auto e : graph[cur]) {
			if (visited[e]) continue;
			visited[e] = true;
			curpath.push_back(e);
			dfs(e);
			curpath.pop_back();
			visited[e] = false;
		}
	};

	for (int i = 0; i < n; ++i) if (graph_in[i].size() == 0) {
		visited[i] = true;
		curpath.push_back(i);
		dfs(i);
		curpath.pop_back();
		visited[i] = false;
	}
	
	//cout << "tgts : "; for (auto e : tgts) cout << nodes[e] << " ";

	for (auto& path : paths) {
		cout << endl;
		for (int i = 1; i < path.size(); i++) {
			if (i != 1) cout << "->";
			cout << "(" << nodes[path[i - 1]] << "," << nodes[path[i]] << ")";
		}
	}

	return 0;
}